package com.liunian.algorithmstudy.tree;

public class BuildTree105 extends TreeNode {

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		int preLen = preorder.length;
		int inLen = inorder.length;
		if (preLen == 0) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[0]);
		int index = 0;
		for (int i = 0; i < inLen; i++) {
			if (inorder[i] == preorder[0]) {
				index = i;
			}
		}
		int[] inorderLeft = processNums(inorder, 0, index);
		int[] inorderRight = processNums(inorder, index + 1, inLen);
		int[] preorderLeft = processNums(preorder, 1, 1 + inorderLeft.length);
		int[] preorderRight = processNums(preorder, 1 + inorderLeft.length, preLen);
		TreeNode leftTree = buildTree(preorderLeft, inorderLeft);
		TreeNode rightTree = buildTree(preorderRight, inorderRight);
		root.left = leftTree;
		root.right = rightTree;
		return root;
	}

	private int[] processNums(int[] nums, int from, int to) {
		int[] res = new int[to - from];
		for (int i = 0; i < to - from; i++) {
			res[i] = nums[i + from];
		}
		return res;
	}

}
